package cn.cxq.learning.divide_and_conquer;

import org.junit.jupiter.api.Test;

/**
 * 剑指offer
 * 连续子数组的最大和 相似的企业真题
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：484994
 * 本题知识点： 分治 动态规划
 *  算法知识视频讲解
 * 题目描述
 * 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
 * 示例1
 * 输入
 * 复制
 * [1,-2,3,10,-4,7,2,-5]
 * 返回值
 * 复制
 * 18
 * 说明
 * 输入的数组为{1,-2,3,10,—4,7,2,一5}，和最大的子数组为{3,10,一4,7,2}，因此输出为该子数组的和 18。
 */
public class SubArray {

    int max = Integer.MIN_VALUE;

    @Test
    public void test() {
        int max = FindGreatestSumOfSubArray(new int[]{2,8,1,5,9});
        System.out.println(max);
    }

    // 使用动态规划的思想，用一个指针max来存遍历到某个位置时的最大值，
    // 用dp数组来存遍历到某个位置时包含该位置数在内时连续子数组求和的最大值。
    public int FindGreatestSumOfSubArray(int[] array) {

        int[] dp = new int[array.length];

        dp[0] = array[0];
        int max = dp[0];

        for (int i = 1; i < array.length; i++) {
            int temp = dp[i-1] + array[i];
            if (temp > array[i]) {
                dp[i] = temp;
            } else {
                dp[i] = array[i];
            }
            if (dp[i] > max) {
                max = dp[i];
            }
        }

        return max;
    }

    //自己的拙作
//    public int FindGreatestSumOfSubArray(int[] array) {
//
//        for (int i = array.length; i > 0; i--) {
//            greatestSum(array, i);
//        }
//
//        return max;
//    }
//
//    private void greatestSum(int[] array, int length) {
//
//        for (int i = 0; i < array.length - length + 1; i++) {
//            int temp = 0;
//            for (int j = i; j < i + length; j++) {
//                temp += array[j];
//            }
//            if (temp > max) {
//                max = temp;
//            }
//        }
//    }
}
